#include <cstdio>
#include <vector>
#include <iostream>
#include <climits>
#include <deque>
using namespace std;
typedef struct
{
	int link;
	int w;
}arc;
typedef struct
{
	bool done;
	bool reach;
	int w;
}vec;
void set(vec c[])
{
	for(int i=0;i<1010;++i)
	{
		c[i].done=false;
		c[i].reach=false;
		c[i].w=-1;
	}
	c[1].reach=true;
	c[1].w=INT_MAX;
}
int main()
{
	int T,n,m,index=1;
	arc t;
	vec c[1010];
	deque<arc> a[1010];
	cin>>T;
	while(T--)
	{
		cin>>n>>m;
		for(int i=1;i<=n;i++)
		{
			if(!a[i].empty())
				a[i].clear();
		}
		while(m--)
		{
			int i,j;
			//cin>>i>>j>>t.w;
			scanf("%d%d%d",&i,&j,&t.w);
			t.link=j;
			a[i].push_back(t);
			t.link=i;
			a[j].push_back(t);
		}
		set(c);
		while(1)
		{
			int i,max,pos=-1,l;
			for(i=1,max=-1;i<=n;++i)
			{
				if(!c[i].done&&c[i].reach)
				{
					if(c[i].w>max)
					{
						max=c[i].w;
						pos=i;
					}
				}
			}
			c[pos].done=true;
			if(pos==n) break;
			for(i=0,l=a[pos].size();i<l;++i)
			{
				int link=a[pos][i].link,w=a[pos][i].w;
				if(!c[link].done)
				{
					if(c[link].w<(c[pos].w<w?c[pos].w:w))
					c[link].w=c[pos].w<w?c[pos].w:w;
					c[link].reach=true;
				}
			}
		}
		cout<<"Scenario #"<<index++<<":"<<endl;
		cout<<c[n].w<<endl<<endl;
	}
	return 0;
}
